//
// Created by Administrator on 2021/7/27.
//

//给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int> &nums) {
        vector<vector<int>> ans;
        backtrack(ans, nums, 0, (int) nums.size());
        return ans;
    }
    /**
     *
     * @param res    结果数组
     * @param output 当前排列
     * @param first  当前进行的位置
     * @param len    目标长度
     */
    void backtrack(vector<vector<int>> &res, vector<int> &output, int first, int len) {
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组  用swap代替一个维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            swap(output[i], output[first]);
        }
    }
};

int main() {
    vector<int> nums{1, 2, 3};
    Solution solution;
    auto ans = solution.permute(nums);
    for (auto &row:ans) {
        for (auto &col:row) {
            cout << col;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}